package 回溯;
import java.util.List;

import org.junit.Test;

import java.util.LinkedList;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
public class leetcode77组合 {
	/*
	 * 另外一种形式的 递归回溯  居然 比这个  版本的快些  
	 * 下面 去 搞明白 一下   快在 那个地方
	 * 快的原因 好像 是找到了  两者的时间复杂度 可能 是一样 的  但 卡尔那种回溯 就是快一些 而且 还可以进行剪枝操作 
	 */
	static int a,b;
	public static void main(String []args) {
		long t1=System.currentTimeMillis();
//		System.out.println(solution(4,2));
		solution(20,5);
		long t2=System.currentTimeMillis();
		long t3=System.currentTimeMillis();
//		System.out.println(solution1(4,2));
		solution1(20,5);
		long t4=System.currentTimeMillis();
		System.out.println(t2-t1);
		System.out.println(t4-t3);
		System.out.printf("a = %d , b = %d",a,b);
	}
	public static List<List<Integer>> solution(int n,int k){
		List<List<Integer>> ans = new ArrayList<>();
		LinkedList<Integer> path =new LinkedList<>();
		process(n,1,k,path,ans);
//		List<List<Integer>> ans1=new ArrayList<>();
//		process1();
		return ans;
	}
	public static void process(int n,int index,int k,LinkedList<Integer>path,
			List<List<Integer>> ans) {
//		if(index == n+2) {
//			return ;
//		}
		a++;
		if(path.size() == k) {
			ans.add(new ArrayList<>(path));
			return ;// the return is necessary;
		}
		if(index == n+1) {
			return ;
		}
		path.add(index);
		process(n,index+1,k,path,ans);
		path.removeLast();
		process(n,index+1,k,path,ans);
	}
//	public static void solution1(int n,int k) {
//		
//	}
	public static List<List<Integer>> solution1(int n,int k){
		List<List<Integer>> ans = new ArrayList<>();
		LinkedList<Integer> path =new LinkedList<>();
		process1(n,1,k,path,ans);
//		List<List<Integer>> ans1=new ArrayList<>();
//		process1();
		return ans;
	}
	public static void process1(int n,int index,int k,LinkedList<Integer> path
			,List<List<Integer>> ans) {
		b++;
		if(path.size() == k) {
			ans.add(new ArrayList<>(path));
			return ;//  不是必须的  减少了一点点 步骤
		}
		// 什么 时候  这里需要 添加 一个变量来  接收值 这是个值得思考的问题
		for(int i = index; i <= n && i <= n-(k - path.size())+1;i++) {
			path.add(i);
			process1(n,i+1,k,path,ans);
			path.removeLast();
		}
	}
	
	/**
	 * 更新时间 2022 9 24号
	 */
	/**
	 * 给定一个数组 choice [] 长度 为 n
	 * 1. 从数组中选取  k 元素 
	 * 	--① :结果集的 list 给返回
	 * 	--②：：结果的个数 （这个可以转换成dp）
	 * 2. 给定一个 值 value  k 从中选取 和 为 k 的元素 (并且限制元素的个数 m )
	 *   -- 同样的是 上面  1 这种情况的 两种问法
	 * 3. 考虑去 重
	 *   -- 数组元素 唯一 不需要去重,数组元素有重复的 情况需要去重 
	 * 4. 可以再提出一个问题 就是 ;
	 *    上面的三种 问题都是 基于 choice 数组 中的 元素不可重复 选择的情况
	 *    可重复选择的话 还需要考虑 这个   每层的 for 循环的 起始点  i 的取值(这样一说其实就很简单了)  
	 */
	// 问题 1. 选取 k个元素 
	/**
	 * 这种回溯问题的优化 ,优化(减少)节点   (就是 减少 for 循环 )
	 *  && choice.length - i >= k - path.size()
	 */
	public static void solution2(int [] choice,List<List<Integer>> ans,Deque<Integer> path,int index,int k) {
		if(path.size() == k) {
			ans.add(new ArrayList<>(path));
			return ;
		}
		for(int i = index;i < choice.length && choice.length - i >= k - path.size();i++) {
			path.addLast(choice[i]);
			solution2(choice,ans,path,i + 1,k);
			path.removeLast();
		}		
	}
	
	// 返回 满足 要求的 结果 个数 (而不是过程) (dp 比较擅长 处理 结果 回溯 处理过程)
	/**
	 * 既然是处理 结果 
	 * 那达成这个 结果的 过程 我就不在意 了
	 * 我只在意 结果 
	 * @return
	 */
	public static int solution3(int choice[],int index,int k,Deque<Integer> path) {
		if(path.size() == k) {
			return 1;
		}
		int ans = 0;
		for(int i = index;i < choice.length && choice.length - i >= k - path.size(); i++) {
			path.addLast(choice[i]);
			ans +=solution3(choice,i + 1,k,path);
			path.removeLast();
		}
		return ans;
	}
	
	@Test
	public void testsolution2() {
		int choice[] = {1,2,3,5,7};
		List<List<Integer>> ans = new ArrayList<>();
		Deque<Integer> path = new ArrayDeque<>();
		solution2(choice,ans,path,0,3);
		int result = solution3(choice,0,3,path);
		System.out.println(ans.size());
		System.out.println(result);
	}
	
	
	// 问题二   从choice 选取 m 个元素使其 和 为 k 的 
	/**
	 * dp 
	 * 相关
	 * 怎么 去重的这个问题
	 * 先简单 一点  先写没有  数目限制 (m)
	 * 	if(rest == 0) {
			ans.add(new ArrayList<>(path));
			return 1;
		}
		
		if(index == choice.length || rest < 0)
			return 0;
		
		这两条件的 顺序 会影响最终的 结果 (有点窒息)
		关键 的 basecase 出在 index == choice.length 
		index == choice.length 这是 造成 结果集减少的一个 致命的原因 
		解释:
		主要是存在 这样的结果集  情况:
		刚好  solution(rest - choice[i] ,i+1)
		此时 rest - choice[i] == 0 i + 1 = choice.length 
		此时达到 (书写顺序不当的 basecase ) 的时候  
		首先的basecase 是
		if(index == choice.length || rest < 0)
			return 0;
		那这样的 话正确的 这种 结果 没有被 计算在内
	 */
	public static int solution4(int choice[] ,int index,List<List<Integer>> ans,Deque<Integer> path,int rest) {
		// 这里的  第一个表达式必须写   第二个 (rest < 0) 这个条件可以进行小小的优化 
		if(rest == 0) {
			ans.add(new ArrayList<>(path));
			return 1;
		}
		if(rest < 0)
			return 0;
//		if(index == choice.length || rest < 0)
//			return 0;
		int res = 0; 
								// 这里等下sort 之后 可以优化
		for(int i = index;i < choice.length;i++) {
			path.addLast(choice[i]);
		    res +=solution4(choice,i,ans,path,rest - choice[i]);
			path.removeLast();
		}
		return res;
	}
	
	@Test
	public void testsolution4() {
		int choice[] = {7,2,2,3,5,1};
//		int choice[] = {1,2,3,5,7};
		List<List<Integer>> ans = new ArrayList<>();
		Deque<Integer> path = new ArrayDeque<>();
//		solution2(choice,ans,path,0,3);
		int res = solution4(choice,0,ans,path,10);
		System.out.println(ans);
		System.out.println(res);
	}
	/**
	 *  去重条件
	 *  在排序条件的基础上 进行 
	 *  去重 和 剪枝
	 *  （排序后 相同的元素 是在 挨着的位置便于去重 ）
	 *  剪枝 （排序之后 元素都是从小到大的 排列   如果当前元素不满足条件 那后面 可以 跳过 （对于该题来说））
	 *  
	 */
	static int test5;
	public static int solution5(int choice [],int index,List<List<Integer>> ans,Deque<Integer> path,int rest) {
		test5++;
		if(rest == 0) {
			ans.add(new ArrayList<>(path));
			return 1;
		}
		if(index == choice.length) {
			return 0;
		}
		/**
		 * 有两种去重的方式
		 * 下面这是 这是一种
		 * 还有一种是用  used[] 数组来
		 * 去重 
		 * # 去重的关键在于  ** 树枝去重**  还是树层去重
		 */
		int res = 0;
		for(int i = index;i < choice.length && rest - choice[i] >= 0;i++) {
			if(i > index && choice[i] == choice[i -1])
				continue;
			path.addLast(choice[i]);
			res += solution5(choice,i,ans,path,rest - choice[i]);
			path.removeLast();
		}
		return res;
	}
	
	@Test
	public void testsolution5() {
		int choice[] = {7,2,2,3,5,1};
		List<List<Integer>> ans = new ArrayList<>();
		Deque<Integer> path = new ArrayDeque<>();
		Arrays.sort(choice);
//		System.out.println(Arrays.toString(choice));
		System.out.println(solution5(choice,0,ans,path,10));
		System.out.println(ans);
		System.out.println(test5);
	}
	
	/**
	 *要 或不要 这种写法 来写
	 *这种 目前来说 (如果元素可重复选的话 好像写不出来) (写出来了)
	 *不可重复 选择
	 *这个去重的 solution 是 错误的
	 */
	static int test;
	public static int solution6(int [] choice,int index,List<List<Integer>> ans,Deque<Integer> path,int rest) {
		test++;
		if(rest == 0) {
			ans.add(new ArrayList<>(path));
			return 1;
		}
		if(index == choice.length)
			return 0;
		int res = 0;
//		boolean flag = index > 0 && choice[index - 1] == choice[index];
		// 要当前元素
		if(rest - choice[index] >= 0) {
		path.addLast(choice[index]);
		 res =solution6(choice,index + 1,ans,path,rest - choice[index]);
		path.removeLast();
		}
		// 不要当前元素 (直接跳到下层 ,rest 什么也不做)
//		if(index > 0 && choice[index] == choice[index - 1])
//			return 0;
//		boolean flag = (index > 0 && choice[index] == choice[index - 1]);
//		if(!flag)
		res += solution6(choice,index + 1,ans,path,rest);
		return res;
	}
	
	@Test
	public void testsolution6() {
//		int choice[] = {7,2,3,2,5,1};
		int choice[] = {1,2,2,3,5,7};
		List<List<Integer>> ans = new ArrayList<>();
		Deque<Integer> path = new ArrayDeque<>();
		int ways = solution6(choice,0,ans,path,10);
		System.out.println(ways);
		System.out.println(ans);
		System.out.println(ans.size());
		System.out.println(test);
	}
	
	/**
	 *要 或不要 这种写法 来写
	 *这种 目前来说 (如果元素可重复选的话 好像写不出来)
	 * 可重复 选择每个元素
	 */
	static int test7;
	public static int solution7(int [] choice,int index,List<List<Integer>> ans,Deque<Integer> path,int rest) {
		test7++;
		if(rest == 0) {
			ans.add(new ArrayList<>(path));
			return 1;
		}
		if(index == choice.length)
			return 0;
		int res = 0;
//		// 要当前元素
//		if(rest - choice[index] >= 0) {
//		path.addLast(choice[index]);
//		 res =solution7(choice,index,ans,path,rest - choice[index]);
//		path.removeLast();
//		}
		// 要当前元素
		if(rest - choice[index] < 0)
			return 0;
			
		path.addLast(choice[index]);
		 res =solution7(choice,index + 1,ans,path,rest - choice[index]);
		path.removeLast();
		
		
		// 不要当前元素 (直接跳到下层 ,rest 什么也不做)
		res += solution7(choice,index + 1,ans,path,rest);
		return res;
	}
	
	@Test
	public void testsolution7() {
//		int choice[] = {7,2,3,5,1};
		int choice[] = {1,2,2,3,5,7};
		List<List<Integer>> ans = new ArrayList<>();
		Deque<Integer> path = new ArrayDeque<>();
		System.out.println("hello world!");
		int ways = solution7(choice,0,ans,path,10);
		System.out.println(ways);
		System.out.println(ans);
		System.out.println(test7);
	}
	
	/**
	 *采用used [] 数组 来辅助 
	 *进行去重 
	 * 
	 */
	static int test8;
	public static int solution8(int [] choice,int index,List<List<Integer>> ans,Deque<Integer> path,int rest,
			boolean used[]) {
		test8++;
		if(rest == 0) {
			ans.add(new ArrayList<>(path));
			return 1;
		}
		if(index == choice.length)
			return 0;
		int res = 0;
//		// 要当前元素
//		if(rest - choice[index] >= 0) {
//		path.addLast(choice[index]);
//		 res =solution7(choice,index,ans,path,rest - choice[index]);
//		path.removeLast();
//		}
		// 要当前元素
		if(rest - choice[index] < 0)
			return 0;
		
		// 去重 条件 一定是 在  **要 当前元素的时候 进行判断**
		boolean flag = index > 0 && choice[index - 1] == choice[index] && used[index - 1] == false;
		if(!flag) {
			used[index] = true;
			path.addLast(choice[index]);
			res =solution8(choice,index + 1,ans,path,rest - choice[index],used);
			path.removeLast();
			used[index] = false;
		}	
		// 不要当前元素 (直接跳到下层 ,rest 什么也不做)
		res += solution8(choice,index + 1,ans,path,rest,used);
		return res;
	}
	@Test
	public void testsolution8() {
//		int choice[] = {7,2,3,5,1};
		int choice[] = {1,2,2,3,5,7};
		List<List<Integer>> ans = new ArrayList<>();
		Deque<Integer> path = new ArrayDeque<>();
		Arrays.sort(choice);
		boolean used[] = new boolean [choice.length];
		int ways = solution8(choice,0,ans,path,10,used);
		System.out.println(ways);
		System.out.println(ans);
		System.out.println(test8);
	}
	
	
	
	//**************下面是           dp 的 代码    ******************************
  
  /**
   *dp的编号对应着  从哪个 solution 改过来的
   *
   *dp6  即 是 从 递归 solution6 改写过来的
   *  
   * 
   */
	public static int dp6(int choice[],int target) {
		int len = choice.length;
		int dp[][] = new int [len + 1][target + 1];
		
		dp[len][0] = 1;
		for(int index = len - 1;index >= 0; index--) {
			dp[index][0] = 1;
			for(int rest = 1;rest <= target;rest++) {
				if(rest - choice[index] >= 0)
					dp[index][rest] = dp[index + 1][rest - choice[index]];
				dp[index][rest] += dp[index + 1][rest]; 
			}
		}
		
		return dp[0][target];
		
	}
	@Test
	public void testdp6() {
		int choice[] = {1,2,2,3,5,7};
		int ans = dp6(choice,10);
		System.out.println(ans);
	}
	/**
	 * 记忆化搜索
	 * 
	 */
	public static int solutionByMemorySearch(int choice[],int target) {
		int len = choice.length;
		int dp[][] = new int[len + 1][target + 1];
		/**
		 * 这里进行 dp 数组的初始化
		 * 的理由是 dp 数组的值 默认是 0 会  缓存表中的 值产生 影响
		 * 因为 当 dp[index][rest] = 0 的时候  无法确定
		 * 该值  被计算过是 0 ,还是 默认是 0;
		 */
		for(int i = 0;i <= len;i++) {
			for(int j = 0;j <=  target;j++) {
				dp[i][j] = -1;
			}
		}
		boolean used [] = new boolean [len];
		memorySearch(choice,0,target,dp,used);
		
		return dp[0][target];
	}
	
	public static int memorySearch(int choice[],int index,int rest,int dp[][],boolean used[]) {
		if(dp[index][rest] != -1) {
			return dp[index][rest];
		}
		if(rest == 0) {
			return dp[index][rest] = 1;
		}
		if(index == choice.length)
			return dp[index][rest] = 0;
		// 剪枝
		if(rest - choice[index] < 0)
			return dp[index][rest] = 0;
//			return 0;
		boolean flag = index > 0 && choice[index] == choice[index - 1] && used[index - 1]  == false;
		int ans = 0;
		// 要
		if(!flag) {
		used[index] = true;
		ans = memorySearch(choice,index + 1,rest - choice[index],dp,used);
		used[index] = false;
		}
		// 不要
		ans += memorySearch(choice,index + 1,rest,dp,used);
		return dp[index][rest] = ans;
	}
	
	@Test
	public void testmemorySearch() {
		int choice[] = {1,2,3,5,7};
		
		System.out.println(solutionByMemorySearch(choice,10));
		
	}
}
